package www.study.com;

//找出字符串中第一个匹配项的下标 https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
//详见《左程云代码面试指南》
public class code29 {
    public static void main(String[] args) {

    }

    class Solution {
        public int strStr(String haystack, String needle) {
            if(haystack == null || needle == null || haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
            char[] ss = haystack.toCharArray();
            char[] mm = needle.toCharArray();
            int[] next = getNext(mm);
            int si = 0;
            int mi = 0;
            while(si < ss.length && mi < mm.length){
                if(ss[si] == mm[mi]){
                    si++;
                    mi++;
                }else if(next[mi] == -1){
                    si++;
                }else{
                    mi = next[mi];
                }
            }
            return mi == mm.length ? si - mi : -1;
        }
        public int[] getNext(char[] match){
            if(match.length == 1) return new int[]{-1};
            int[] next = new int[match.length];
            next[0] = -1;
            next[1] = 0;
            int pos = 2;
            int cn = 0;
            while(pos < match.length){
                if(match[pos - 1] == match[cn]){
                    next[pos++] = ++cn;
                }else if(cn > 0){
                    cn = next[cn];
                }else{
                    next[pos++] = 0;
                }
            }
            return next;
        }
    }
}
